package m202403.d14;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/3/14 13:50
 */
//5. 最长回文子串
public class Q5 {

    public static void main(String[] args) {
        System.out.println(new Q5().longestPalindrome("cbbd"));
    }

//    public String longestPalindrome(String s) {
//        boolean[][] dp = new boolean[s.length()][s.length()];
//
//        for (int i = 0; i < s.length(); i++) {
//            dp[i][i] = true;
//        }
//
//        int start = 0;
//        int end = 0;
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = 0; j < i; j++) {
//                if (s.charAt(i) != s.charAt(j)) {
//                    dp[i][j] = false;
//                } else {
//                    if (i - j == 1) {
//                        dp[i][j] = true;
//                    } else {
//                        dp[i][j] = dp[i - 1][j + 1];
//                    }
//                }
//                if (dp[i][j] && end - start < i - j) {
//                    start = j;
//                    end = i;
//                }
//            }
//        }
//        return s.substring(start, end + 1);
//    }

    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }

        int start = 0;
        int end = 0;
        //回文串长度
        for (int l = 2; l <= s.length(); l++) {
            //回文串开始位置
            for (int i = 0; i < s.length(); i++) {
                int j = i + l - 1;
                if (j >= s.length()) {
                    break;
                }
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i == 1) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if (dp[i][j]) {
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}
